#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <time.h>
#define Max 10000

long fibo(long n)
{
	if (n==1 || n==2) return 1;

	int a[Max];
	int i;
	a[0] = 0;
	a[1] = 1;
	for(int i = 2; i<=n; i++)
	{
		a[i] = a[i-1] + a[i-2];
	}
	return a[n];
	
	return (fibo(n-1) + fibo(n-2));	
}

long sum(long n)
{	long s = 0;
	for(long i = 1; i<n+1; i++)
		s = s+ (i*i);
	//long a = fibo(44);
	return s;	
}

void main()
{
	long n=10;
	//printf("n=");
	//scanf("%d", &n);
	//time begin
	int N[1000];
	for(int i = 1; i < 10; i++)
	{
		N[i] = 100*i;
	}
	
	for(int i = 1; i < n; i++)
	{
		
		clock_t start = clock();
		//printf(fibo(N[i])+ "");
		printf("fibo(%d) = %d | ", N[i], fibo(N[i]));	
		printf("     Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);	

		getch();
	//time end	
	}
}
